Financial transactions are beginning to be offered in wired networks, such as the world wide web, and are desirable in wireless networks, such as paging networks and cellular networks. The need for secure communication of financial transactions is paramount in order for them to be successfully used in such environments. Methods of providing the needed security include the use of finite field arithmetic, such as Galois Field (GF) arithmetic, for encryption and decryption of secure messages. For optimal speed of calculations using Galois Field arithmetic, Galois Field arithmetic logic units (ALUs) that are designed especially for Galois Field arithmetic are employed. One implementation of a Galois Field ALU is a special-purpose ALU that implements addition (subtraction), squaring, multiplication, and inverse in a finite field. A specific Galois Field typically used is a field with 2.sup.M elements, denoted by GF(2.sup.M). Herein, M is called the field size. Any element in the field (there are 2.sup.M total) can be represented as an M-bit binary string. This field is closed under all of the above operations. Closed essentially means that the result of performing any of these arithmetic operations always is another element in the field.
An example of a prior art Galois Field ALU is described herein as one which provides the functions of Galois Field addition (GF addition), GF squaring, and GF multiplication. Other functions, such as the important function of finding a GF inverse (GF inversion) can be performed using combinations of one or more of the three functions of GF addition, GF squaring, and GF multiplication. Examples of an ALU providing these three functions are described herein using a GF(2.sup.6), which has 64 elements. Each of the 64 elements in the GF(2.sup.6) is preferably represented by a unique 6 bit pattern. (There are exactly 64 unique patterns possible.)
FIG. 1 is an electrical block diagram of a prior art GF ALU 100 of size M=6 that shows the GF ALU 100 configured for the GF addition function. The GF ALU 100 comprises an A field element register 105 and a B field element register 110 which are input registers, a C field element register 115, which is a result field element register, and logic gates 130. The A, B, and C field element registers 105, 110, 115 each comprise, respectively, six single bit registers 120, that are identified as single bit registers A0' to A5', B0' to B5', and C0' to C5', each comprising a conventional D input 121, a conventional Q output 122, and a conventional clock input 123. The A, B, and C field element registers 105, 110, 115 further comprise six switches 135, having one switch coupled to each D input 121. The GF ALU 100 comprises logic gates other than logic gates 130, and the switches 135 have inputs other than those shown in FIG. 1, as will be described with reference to FIGS. 2 and 3. A control signal (not shown in FIGS. 1-6) that is coupled to each of the switches selects one of the inputs to each switch in a conventional manner, depending on the configuration needed to perform the desired function, and couples the selected input to the D input of the associated single bit register 120. FIG. 1 shows a configuration of the GF ALU 100 after the single bit registers 120 of the A and B field element register 105, 110 have been loaded with bits A0-A5 and B0-B5 of first and second GF elements. (The bits are coupled to the switches 135 by paths not shown in FIG. 1.) Thus, the values at the Q outputs 122 of the A and B field element registers 105, 110 have the values A0-A5 and B0-B5 that have been loaded.
The outputs 122 of the single bit registers 120 of the GF ALU 100 are logically combined in different manners to perform the three functions cited above. The logical combination is provided by the logic gates 130, the inputs to the logic gates 130 from the single bit registers 120, which are identified by the values A0-A5 and B0-B5 shown at outputs of the single bit registers 122 and at the inputs 129 to the logic gates 130, and a coupling of outputs 131 of the logic gates 130 to the single bit registers 120 of the C field element register 115. In the case of this GF addition function, the logic gates 130 are all conventional Boolean Exclusive OR gates. An output 131 of each of the Boolean Exclusive OR gates 130 is coupled to a D input of one of the single bit registers 120 of the C field element register 115 through one of the switches 135. The coupling of the logic gates 130 is such that when a clock cycle is coupled to the clock inputs 123 of the C field element register 115, the outputs C0-C5 of the C field element register 115 are given by the following equations: EQU C0"=A0+B0 EQU C1"=A1+B1 EQU C2"=A2+B2 EQU C3"=A3+B3 EQU C4"=A4+B4 EQU C5"=A5+B5
After being clocked, the outputs C0"-C5" of the C field element register 115 are those of a GF element that is the GF addition of the A field element and the B field element. In all equations shown herein, the addition operation (+) is implemented by the Boolean Exculsive OR function.
FIG. 2 is an electrical block diagram of a prior art GF ALU 100 that shows the GF ALU 100 configured for the GF squaring function. The GF ALU 100 comprises the A, B, and C field element registers 105, 110, 115, the switches 135, and the logic gates 130 (not shown in FIG. 2). As in the case of the GF addition function described with reference to FIG. 1, the single bit registers 120 of the A field element register 105 have been loaded with bits A0-A5 of a first GF element and the single bit registers 120 of the B field element register 110 have been loaded with bits B0-B5 of a second GF element. The switches 135 control the intercoupling of the single bit registers 120 of the A field element register 105 such that the outputs of each of the single bit registers 120 are coupled to a single bit register 120 of a next higher order (as indicated by a next higher number in the identifiers; e.g., A2' is coupled to A3') of the single bit registers 120. A first clock cycle is applied to the single bit registers 120 of the A field element register 105, which shifts the values that had been loaded to the single bit registers 120 of a next higher order, except for the value in single bit register A5' 120, which is shifted into single bit register A0' 120. The registers are identified with the prime indication to signify that their contents is not necessarily equal to the originally loaded input values (which are designated without the prime indication). The outputs of the single bit registers 120 are also indicated with the prime designation for the same reason. In this squaring configuration of the GF ALU 100, the switches 135 on the D inputs to the single bit registers 120 of the C field element register 115 are controlled such that the outputs A0'-A5' of the single bit registers 120 are coupled to the D inputs 120 on a one for one basis. When a second clock cycle is coupled to the clock inputs 124 of the C field element register 115, the outputs C0-C5 of the C field element register 115 are given by the following equations: EQU C0"=A0'=A5 EQU C1"=A1'=A0 EQU C2"=A2'=A1 EQU C3"=A3'=A2 EQU C4"=A4'=A3 EQU C5"=A5'=A4
The Q outputs of the C field element register 115, comprising the Q outputs C0"-C5", is the squared result of the original input to the A field element register 105. The GF ALU 100 can also be configured to square the GF element B, loaded in the C field element register 115, by control of the switches 135. In alternative embodiment, the output of the GF ALU 100 is generated directly from the A field element register 105 (or the B field element register 110), avoiding a need for the second clock cycle to obtain the result.
It will be appreciated that in general, for Galois Fields of size M, if the Galois Field can be represented in an optimal normal basis, there is a set of GF multiply equations comprising M equations in which each has 2M-1 terms, as is well known to one of ordinary skill in the art. When a multiply function is performed by the GF ALU 100, the values of C0-C5 that must be obtained are given by the GF multiply equations, which are shown below for a Galois Field of size 6: EQU C0=A0B1+A1(B4+B0)+A2(B3+B4)+A3(B2+B5)+A4(B2+B1)+A5(B5+B3) EQU C1=A1B2+A2(B5+B1)+A3(B4+B5)+A4(B3+B0)+A5(B3+B2)+A0(B0+B4) EQU C2=A2B3+A3(B0+B2)+A4(B5+B0)+A5(B4+B1)+A0(B4+B3)+A1(B1+B5) EQU C3=A3B4+A4(B1+B3)+A5(B0+B1)+A0(B5+B2)+A1(B5+B4)+A2(B2+B0) EQU C4=A4B5+A5(B2+B4)+A0(B1+B2)+A1(B0+B3)+A2(B0+B5)+A3(B3+B1) EQU C5=A5B0+A0(B3+B5)+A1(B2+B3)+A2(B1+B4)+A3(B1+B0)+A4(B4+B2)
In the equations shown herein, the product operation is implemented by the Boolean AND function. No symbol is used for the Boolean AND function in the equations--the normal convention of adjacency of two symbols indicates a Boolean AND function of adjacent symbols. It will be appreciated that the above equations could be implemented using a purely combinatorial logic configuration that could be accomplished by sixty 2 input Boolean Exculsive OR gates and thirty 2 input Boolean AND gates. However, this is logic gate intensive and would take up a lot of circuit area, so an alternative has been devised, which is illustrated in FIG. 3.
FIG. 3 is an electrical block diagram of a prior art GF ALU 100 that shows the GF ALU 100 configured for the GF multiply function. The GF ALU 100 comprises the A, B, and C field element registers 105, 110, 115, the switches 135, the logic gates 130 (not shown in FIG. 3), and logic gates 140. As in the case of the GF squaring function described with reference to FIG. 2, the single bit registers 120 of the A field element register 105 are initially loaded with bits A0-A5 of a first GF element and the single bit registers 120 of the B field element register 110 are initially loaded with bits B0-B5 of a second GF element. The switches 135 control the couplings of the Q outputs 122 of each of the single bit registers 120 of the A field element register 105 and the B field element register 110 are coupled to a D input 121 of a single bit register 120 of a next higher order of the respective field element register 105, 110. The logical combination of this multiplying configuration of the GF ALU 100 is provided by the intercoupling of the logic gates 140, by inputs 129 to the logic gates 140 from the single bit registers 120 (which are identified by the values A0'-A5' and B0'-B5' shown at the Q outputs 122 of the single bit registers 120 and at the inputs 129 to the logic gates 140), and a coupling of outputs 141 of the logic gates to the single bit registers 120 of the C field element register 115. In the case of this GF multiply function, the logic gates 140 are conventional Boolean Exclusive OR and AND gates. An output 141 of each of the Boolean Exclusive OR gates 140 is coupled to a D input of one of the single bit registers 120 of the C field element register 115 through one of the switches 135. The logic gates 140 are intercoupled such that when a clock cycle is coupled to the clock inputs 123 of the C field element register 115, the outputs C0"-C5" of the C field element register 115, which are intermediate outputs until a last clock cycle is completed, are given by the following equations: EQU C0"=A0'B1'+C5' EQU C1"=A2'(B5'+B1')+C0' EQU C2"=A4'(B5'+B0')+C1' EQU C3"=A0'(B5'+B2')+C2' EQU C4"=A2'(B0'+B5')+C3' EQU C5"=A4'(B4'+B2')+C4'
In these equations, the single prime notations indicate prior values; that is, the values prior to the clock cycle that generates the double prime values. The single bit registers 120 C0'-C5' are initially loaded with Boolean 0's.
It will be appreciated that the terms of the logical combination for each intermediate value C0"-C5" are the respective term of the GF multiply equations, plus a feed forward term that is the next less significant intermediate value, in a cyclical sense. Thus, for example, C3" is given by the third term of the C3 equation in the GF multiply equations, A0'(B5'+B2'), plus C2'.
It will be further appreciated that when all the single bit registers 120 are clocked simultaneously for six consecutive clock cycles, a GF multiply function is completed and the outputs C0"-C5" after the sixth clock cycle will have the values given by the GF multiply equations for GF(2.sup.6) shown above, shifted by one position (thus, the result for C0 is in C5', the result for C1 is in C0', etc.).
This approach has the advantage of substantially reducing the number of logic gates needed to eleven two input Boolean exclusive OR gates and six Boolean AND gates, but it has a disadvantage of requiring six clock cycles. This decrease in speed is particularly problematic in security related applications because of the number of times the multiply function must be used. It will be appreciated that the speed decrease of the technique used in FIG. 3 is directly proportional to the size, M, of the GF multiply function. In contrast, although the purely combinatorial logic approach is fast, requiring only one clock cycle to load the result into the C field element register, it requires a number of two input logic gates that exceeds 2M.sup.2.
Thus, what is needed is a circuit that performs the GF multiply function more speedily than the circuit described with reference to FIG. 3, but without the large number of gates described above with reference to the purely combinatorial logic approach.